/** ***************************************************************************
 * CoffeeArray.hpp
 * 2012 CoffeeParty Ltd.
 * Date Created: 2012-07-21                                  format YYYY-MM-DD
 * Revision Id: $Id$
 ******************************************************************************
 */

#ifndef _COFFEE_ARRAY_HPP_
#define _COFFEE_ARRAY_HPP_

#include "CoffeeCommons.hpp"
#include "CoffeeAllocator.hpp"

template<class T, typename TAlloc = CoffeeAllocator<T> >
class CoffeeArray
{
public:
    CoffeeArray()
    : array(0), allocated(0), used(0), on_clean(true)
    {
    }

    CoffeeArray(unsigned int count)
    : array(0), allocated(0), used(0), on_clean(true)
    {
        reallocate(count);
    }

    CoffeeArray(const CoffeeArray<T, TAlloc>& other)
    : array(0), allocated(0), used(0), on_clean(true)
    {
        *this = other;
    }

    ~CoffeeArray()
    {
        clear();
    }

    void push_back(const T& element)
    {
        insert(element, used);
    }

    void push_front(const T& element)
    {
        insert(element);
    }

    const CoffeeArray<T, TAlloc>& operator=(const CoffeeArray<T, TAlloc>& other)
    {
        if (this == &other)
            return *this;

        if (array)
            clear();

        if (other.allocated == 0)
            array = 0;
        else
            array = allocator.allocate(other.allocated);

        used = other.used;
        on_clean = true;
        allocated = other.allocated;

        for (unsigned int i = 0; i < other.used; ++i)
            allocator.construct(&array[i], other.array[i]);

        return *this;
    }

    bool operator==(const CoffeeArray<T, TAlloc>& other) const
    {
        if (used != other.used)
            return false;

        for (unsigned int i = 0; i < other.used; ++i)
            if (array[i] != other[i])
                return false;
        return true;
    }

    bool operator!=(const CoffeeArray<T, TAlloc>& other) const
    {
        return !(*this == other);
    }


    T& operator[](unsigned int index)
    {
        try_to_break_if(index >= used);
        return array[index];
    }

    const T& operator [](unsigned int index) const
    {
        try_to_break_if(index >= used);
        return array[index];
    }

    T& getLast()
    {
        try_to_break_if(!used);
        return array[used - 1];
    }

    T* pointer()
    {
        return array;
    }

    const T* const_pointer() const
    {
        return array;
    }

    unsigned int size() const
    {
        return used;
    }

    unsigned int allocated_size() const
    {
        return allocated;
    }

    bool empty() const
    {
        return used == 0;
    }

    int binary_search(const T& element)
    {
        ///< Needs to be sorted before using
        return binary_search(element, 0, used - 1);
    }

    int binary_search(const T& element, int left, int right) const
    {
        if (!used)
            return -1;

        int m;
        do
        {
            m = (left + right) >> 1;
            if (element < array[m])
                right = m - 1;
            else left = m + 1;

        }
        while ((element < array[m] || array[m] < element) && left <= right);

        if (!(element < array[m]) && (array[m] < element))
            return m;

        return -1;
    }

    int binary_search_multi(const T& element, int& last)
    {
        int index = binary_search(element, 0, used - 1);
        if (index < 0)
            return index;

        last = index;

        while (index > 0 && !(element < array[index - 1]) && !(array[index - 1] < element))
            index -= 1;

        while (last < (int)(used - 1) && !(element < array[index + 1]) && !(array[index + 1] < element))
            last += 1;

        return index;
    }

    void set_pointer(T* new_ptr, unsigned int size, bool clean = true)
    {
        clear();
        array = new_ptr;
        allocated = size;
        used = size;
        on_clean = clean;
    }

    void set_used(unsigned int touse)
    {
        if (allocated < touse)
            reallocate(touse);
        used = touse;
    }

    void set_on_clean(bool q)
    {
        on_clean = q;
    }

    void erase(unsigned int index)
    {
        try_to_break_if(index >= used);
        for(unsigned int i = index + 1; i < used; ++i)
        {
            allocator.destruct(&array[i - 1]);
            allocator.construct(&array[i - 1], array[i]);
        }

        allocator.destruct(&array[used - 1]);
        --used;
    }

    void clear()
    {
        if (on_clean)
        {
            for (unsigned int i = 0; i < used; ++i)
                allocator.destruct(&array[i]);

            allocator.deallocate(array);
        }

        array = 0;
        used = 0;
        allocated = 0;
    }

protected:
    void insert(const T& element, unsigned int index = 0)
    {
        try_to_break_if(index > used);

        if (used + 1 > allocated)
        {
            const T e(element);
            unsigned int new_alloc;
            new_alloc = used + 1;
            reallocate(new_alloc);

            for (unsigned int i = used; i > index; --i)
            {
                if (i < used)
                    allocator.destruct(&array[i]);
                allocator.construct(&array[i], array[i - 1]);
            }

            if (used > index)
                allocator.destruct(&array[index]);
            allocator.construct(&array[index], e);
        }
        else
        {
            if (used > index)
            {
                allocator.construct(&array[used], array[used - 1]);
                for (unsigned int i = used - 1; i > index; --i)
                {
                    array[i] = array[i - 1];
                }
                array[index] = element;
            }
            else
            {
                allocator.construct(&array[index], element);
            }
        }

        ++used;
    }

private:
    void reallocate(unsigned int newsize)
    {
        T* old_array = array;
        array = allocator.allocate(newsize);
        allocated = newsize;

        int end = used < newsize ? used : newsize;

        for (int i = 0; i < end; ++i)
            allocator.construct(&array[i], old_array[i]);

        for (unsigned int j = 0; j < used; ++j)
            allocator.destruct(&old_array[j]);

        if (allocated < used)
            used = allocated;

        allocator.deallocate(old_array);
    }

    T* array;
    TAlloc allocator;
    bool on_clean: 1;
    unsigned int allocated;
    unsigned int used;
};

#ifndef c_array
# define c_array CoffeeArray
#endif

#endif /** _COFFEE_ARRAY_HPP_ */
